'''
https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/
'''
from collections import Counter


class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        ans = 0
        for i in range(1,27):       #分治：遍历可能的字符种类数量（1~26）
            cnt = Counter()     #计数
            unique = 0          #字符种类
            num_k = 0           #满足出现次数大于等于k的字符串数量
            left = 0
            for right,char in enumerate(s):
                if cnt[char] == 0:
                    unique += 1
                cnt[char] += 1

                if cnt[char] == k:
                    num_k += 1
                #当字符串种类超过i时，移动左窗口
                while unique > i:
                    left_char = s[left]
                    if cnt[left_char] == k:
                        num_k -= 1      #因为要一直移动左窗口，所以计数会一直减少，当进入循环时刚好==k时，再减一后，num_k就要减一了
                    cnt[left_char] -= 1
                    if cnt[left_char] == 0:     #如果减完了，种类就少一个
                        unique -= 1
                    left += 1
                if unique == i and num_k == i:      #当种类满足要求，且子串里的数量都满足>=k时，就更新ans
                    ans = max(ans ,right - left +1)
        return ans